﻿#pragma once
namespace bit
{
	//struct和class：如果有区分共有和私有，用class，全共有一般都用struct
	template<class T>
	struct ListNode//class ListNode当前不会报错，但是
	{
	public://如果不public那么这些私有的变量和初始化函数无法被访问，除非用友元
		ListNode<T>* _next;
		ListNode<T>* _prev;

		T _data;
		//为下面的new Node写构造函数
		ListNode(const T& data = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(data)
		{}
	};
	//因为模板是不会被细节编译的，模板要实例化以后才会被编译
	//不实例化就也不会报错
	//按需实例化：（调用哪个成员函数才会实例化哪个成员函数）类的实例化也不会实例化所有的成员函数，只有当调用的时候才会被编译，错误才会显示


//
//	//对于不连续的物理空间，可以封装实现表层的连续
//	//封装到一个类里面的作用****
//	//一个类可以去重载运算符：进行++，--（来满足我们想要的行为）
//	template<class T>
//	class ListIterator//这个类可以定义成list的内部类，但是不建议：
//	{
//		typedef ListIterator Self;
//		typedef ListNode<T> Node;
//		Node* _node;//包含一个节点的指针
//	public:
//		//定义节点的迭代器：用节点的指针作为参数
//		ListIterator(Node* node)
//			:_node(node)//成员：指针_node
//		{}
//		//拷贝构造：浅拷贝即可
//		//两个迭代器都指向同一个节点：默认生成的拷贝构造就够用
//		//没有显示写析构，就不需要写拷贝构造
//
//
//		//++it(返回地址)
//		Self& operator++()
//		{
//			_node = _node->_next;//跳转到下一个位置，再返回当前的这个位置*this
//			return *this;
//		}
//		Self& operator--()
//		{
//			_node = _node->_prev;//跳转到下一个位置，再返回当前的这个位置*this
//			return *this;
//		}
//		//加一个形参区分前置后置++，--
//		//并且要返回++之前的值：先保存
//		//不能再传引用，因为返回的不是同一块
//		Self operator++(int)
//		{
//			Self tmp(*this);//用指针来初始化一个tmp来存储this指针
//			_node = _node->_next;//跳转到下一个位置，再返回当前的这个位置*this
//			return *this;
//		}
//		Self operator--(int)
//		{
//			Self tmp(*this);
//			_node = _node->_prev;//跳转到下一个位置，再返回当前的这个位置*this
//			return tmp;
//		}
//		//+n不用重载：效率不高，o（n）库里的list迭代器也不支持
//
//		
//		//返回节点
//		T& operator*()
//		{
//			return _node->_data;//返回一个指向——data数据的节点
//		}
//		//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·
//		//it->row(访问类里面装的数据)
//		T* operator->()
//		{
//			return &_node->_data;//箭头访问,返回的是T这个类的地址pos*//指向——data数据的节点指针
//		}
//
//
//		//传入一个迭代器（比较的位置）
//		bool operator!=(const Self& it)
//		{
//			return _node != it._node;//比较当前的node和it位置的node
//		}
//		bool operator==(const Self& it)
//		{
//			return _node == it._node;//比较当前的node和it位置的node
//		}
//
//	};

	//const迭代器核心要修改的是：operator*和operator->
	template<class T, class Ref, class Ptr>
	class ListIterator//这个类可以定义成list的内部类，但是不建议：
		//可以写成struct（全公有）
	{
		typedef ListIterator Self;//改个名字和可修改内容的迭代器区分
		typedef ListNode<T> Node;

	public:
		Node* _node;//包含一个节点的指针

		//定义节点的迭代器：用节点的指针作为参数
		ListIterator(Node* node)
			:_node(node)//成员：指针_node
		{}
		//拷贝构造：浅拷贝即可
		//两个迭代器都指向同一个节点：默认生成的拷贝构造就够用
		//没有显示写析构，就不需要写拷贝构造


		//++it(返回地址)
		Self& operator++()
		{
			_node = _node->_next;//跳转到下一个位置，再返回当前的这个位置*this
			return *this;
		}
		Self& operator--()
		{
			_node = _node->_prev;//跳转到下一个位置，再返回当前的这个位置*this
			return *this;
		}
		//加一个形参区分前置后置++，--
		//并且要返回++之前的值：先保存
		//不能再传引用，因为返回的不是同一块
		Self operator++(int)
		{
			Self tmp(*this);//用指针来初始化一个tmp来存储this指针
			_node = _node->_next;//跳转到下一个位置，再返回当前的这个位置*this
			return *this;
		}
		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;//跳转到下一个位置，再返回当前的这个位置*this
			return tmp;
		}
		//+n不用重载：效率不高，o（n）库里的list迭代器也不支持


		//返回引用
		Ref operator*()
		{
			return _node->_data;//返回一个指向——data数据的节点
		}
		//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·
		//it->row(访问类里面装的数据)
		Ptr operator->()
		{
			return &_node->_data;//箭头访问,返回的是T这个类的地址pos*//指向——data数据的节点指针
		}


		//传入一个迭代器（比较的位置）
		bool operator!=(const Self& it)
		{
			return _node != it._node;//比较当前的node和it位置的node
		}
		bool operator==(const Self& it)
		{
			return _node == it._node;//比较当前的node和it位置的node
		}

	};





	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		//迭代器：typedef Node* iterator;
		//❌：因为链表的地址空间非连续，对这个迭代器++不能+类型的大小移到下一个节点
		//then...
		//不能用上面的方法，但是思路都是通过++来达到挪动到下一个节点的结果：
		//如何实现？
		//node*不符合我们需要的迭代器类型；但是
		//可以用一个类来封装这些节点的指针！
		typedef ListIterator<T, T&, T*> iterator;//规范迭代器，名字都改为规范的iterator（也可以不用规范的名字）
		typedef ListIterator<T, const T&, const T*> const_iterator;
		//可以通过模板参数来控制返回值
		//让这个模板实例化成两个类
		//不用自己重新写，直接交给编译器自己生成：识别类，然后自动生成适合的函数

		//模板内加两个类模板，传不同的模板参数，来交给编译器处理
		//写多两个模板参数T&(Ref)，T*(Ptr),const T&,const T*
		//根据两种修改模式，添加一个迭代器
		//普通可修改迭代器内部，将返回的值替换为（模板）template<里面的类>
		//类模板包含：根据两种修改模式：分别包含可修改和不可修改，
		// 根据调用的const_iterator，或者iterator，编译器来自适应的改变返回的类型


		iterator begin()//返回第一个位置的位置：head->next
		{
			//begin迭代器用一个节点的指针来构造
			return iterator(_head->_next);
		}
		const_iterator begin() const//返回第一个位置的位置：head->next
		{
			//begin迭代器用一个节点的指针来构造
			return const_iterator(_head->_next);
		}

		iterator end()//返回最后一个节点的下一个位置：tail->next，也就是head
		{
			return iterator(_head);
		}
		const_iterator end() const//返回最后一个节点的下一个位置：tail->next，也就是head
		{
			return const_iterator(_head);
		}


		//初始
		//list()
		//{
		//	//一个结构体，将内部初始化为：前驱后继都指向自己：一个节点
		//	_head = new Node(T());//给值初始化data：T类型的对象
		//	//像这种自定义类型的对象给值初始化：！！！可以用匿名对象T（）
		//	_head->_next = _head;
		//	_head->_prev = _head;
		//}
		//void push_back(const T& x)//要尾插：先找尾，新节点，tailnext指向newnode，newnodeprev指向tail，新next指向head，headprev指向newnode
		//{
		//	Node* newnode = new Node(x);
		//	Node* tail = _head->_prev;

		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//	//链表为空，只有一个头节点，也可以成功运行上面的逻辑
		//}

		//判断沿用上面的初始化(初始化一个头节点)：不传值构造，因为值需要用已有的
		//头节点
		void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}


		list()
		{
			empty_init();
		}

		//深拷贝
		//拷贝构造:lt2(lt1)
		//拷贝构造时，需要先给空的list创建一个头节点
		//这个创建头节点的步骤单独提出来，因为构造和拷贝构造可以一起使用这个步骤
		list(const list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}



		//析构:复用clear清空节点，再删除头节点，并置空
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;

		}

		//clear清空节点：利用erase删除节点实现
		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				/*erase(it);
				++it;*/
				//❌上面这种方式会导致erase以及让it这个迭代器失效，下面的++再进行访问就是访问失效的迭代器，❌
			//应该通过，重新赋值来控制（erase返回的刚好是下一个位置的迭代器，直接进行返回即可
				it = erase(it);
			}
		}




		//insert
		//pos没有迭代器失效
		void insert(iterator pos, const T& x)
		{
			//
			Node* cur = pos._node;//插入的位置迭代器内部的节点(指针)
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;//用指针->访问成员：前驱指针
			//prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}
		//erase
		//pos有迭代器失效（被释放 ）
		//需要一个返回值(下一个位置的迭代器)防止边删边走的情况
		iterator erase(iterator pos)
		{
			//加个断言防止将头节点都删掉
			assert(pos != end());
			Node* cur = pos._node;//插入的位置迭代器内部的节点(指针)
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;
			return iterator(next);
		}

		//尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}

		//尾删
		void pop_back()
		{
			erase(--end());
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}

	private:
		Node* _head;//给一个头结点的指针
	};

	//const迭代器
	// 解决代码冗余
	// 
	// 也定义出了一个类来封装，和可修改迭代器出现大量的重复：如何解决？
	// //可以通过模板参数来控制返回值（实例化两个不同的类）
	// 
	// 
	//不能直接将自己写的iterator加const变成我们要的const迭代器
	//const迭代器的目的是这个迭代器可以++等（修改），但是迭代器指向的内容不能被修改：类似：const T* p

	//*****只需要改名字和* ->的运算符重载部分，还有list内部加上一个可修改迭代器,并添加const的begin（）和end()
	//

	void Func(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();//const的迭代器
		while (it != lt.end())
		{
			//*it += 10;
			//cout << it._node->_data << endl;
			//
			//

			cout << *it << " ";
			++it;
		}
		cout << endl;

	}








	void test_list1()
	{
		//按须实例化：不调用就不实例化这个成员函数
		list<int> lt1;

		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);


		//不可修改的遍历
		Func(lt1);//const的链表


		//~~~~~~遍历~~~~~~(迭代器)
		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			*it += 10;
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	struct Pos
	{
		int _row;
		int _col;

		//没有合适的默认构造：给值
		Pos(int row = 0, int col = 0)
			:_row(row)
			, _col(col)
		{}
	};



	void test_list2()
	{
		list<Pos> lt1;
		lt1.push_back(Pos(100, 100));
		lt1.push_back(Pos(200, 200));
		lt1.push_back(Pos(300, 300));
		list<Pos>::iterator it = lt1.begin();//不能传引用
		while (it != lt1.end())
		{
			cout << (*it)._row << ": " << (*it)._col << endl;//自定义类型没有写流插入，可以用解引用 + .成员
			//pos*访问：->  (也可以用指针 + ->来访问)
			//需要得到pos*

			//所以上面重载的->符号就是为了第二种访问方式准备的
			//cout << it->_row << ":" << it->_col << endl;
			//显示调用的方式：
			cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;
			//it->为了可读性省略了一个->   ！！！！
					//it.operator->()是为了得到pos*这个指针，再->时是访问pos内部的成员
			++it;
		}
		cout << endl;

	}

	void test_list3()
	{
		//按须实例化：不调用就不实例化这个成员函数
		list<int> lt1;

		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);

		Func(lt1);

		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);

		Func(lt1);
		lt1.push_front(10);
		lt1.push_front(20);
		lt1.push_front(30);
		Func(lt1);


		//pop...

	}
	void test_list4()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);
		Func(lt1);

		//拷贝构造：表面上是能跑，但是，是浅拷贝，改变lt1会改变lt2(因为指向同一空间)
		list<int> lt2(lt1);
		Func(lt2);

		lt1.push_back(6);
		Func(lt1);
		Func(lt2);
	}

}
